package interview;

public class interview_08_11 {
    public int waysToChange(int n) {
        //1,5,10,25
        int[][] dp=new int[n+1][4];
        dp[0][0]=1;
        dp[0][1]=0;
        dp[0][2]=0;
        dp[0][3]=0;
        for(int i=1;i<n+1;++i){
            dp[i][0]+=dp[i-1][0];
            dp[i][0]%=1000000007;
            if(i-5>=0){
                dp[i][1]+=dp[i-5][1];
                dp[i][1]%=1000000007;
                dp[i][1]+=dp[i-5][0];
                dp[i][1]%=1000000007;
            }
            if(i-10>=0){
                dp[i][2]+=dp[i-10][2];
                dp[i][2]%=1000000007;
                dp[i][2]+=dp[i-10][0];
                dp[i][2]%=1000000007;
                dp[i][2]+=dp[i-10][1];
                dp[i][2]%=1000000007;
            }
            if(i-25>=0){
                dp[i][3]+=dp[i-25][3];
                dp[i][3]%=1000000007;
                dp[i][3]+=dp[i-25][0];
                dp[i][3]%=1000000007;
                dp[i][3]+=dp[i-25][1];
                dp[i][3]%=1000000007;
                dp[i][3]+=dp[i-25][2];
                dp[i][3]%=1000000007;
            }
        }
        return ((dp[n][0]+dp[n][1])%1000000007+(dp[n][2]+dp[n][3])%1000000007)%1000000007;
    }

}
